package luogu.GraphTheory;
//P1629 邮递员送信
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
//暂时未解决返程还未解决

/**
 * @author :chenjie
 * @date :Created 2023/1/9 15:19
 */
public class PostmanDeliversLetter {
    static int n,m,idx,idx2;
    static int[]dist=new int[1010];
    static int[]e=new int[100010];
    static int[]ne=new int[100010];
    static int[]w=new int[100010];
    static int[]h=new int[1010];
    static int[]e1=new int[100010];
    static int[]ne1=new int[100010];
    static int[]w1=new int[100010];
    static int[]h1=new int[1010];
    static boolean[]st=new boolean[1010];
    static Queue<int[]> queue=new PriorityQueue<>((a,b)->{return a[1]-b[1];});
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Arrays.fill(h,-1);
        Arrays.fill(h1,-1);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
            add2(b,a,c);
        }
        dj();
        int sum=0;
        for (int i = 1; i <= n; i++) {
            sum+=dist[i];
        }
        dj2();
        for (int i = 1; i <= n; i++) {
            if(dist[i]==0x3f3f3f3f){
                continue;
            }
            sum+=dist[i];
        }
        System.out.println(sum);

    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        ne[idx]=h[a];
        w[idx]=c;
        h[a]=idx++;
    }
    public static void add2(int a,int b,int c){
        e1[idx2]=b;
        ne1[idx2]=h1[a];
        w1[idx2]=c;
        h1[a]=idx2++;
    }
    public static void dj(){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        queue.offer(new int[]{1,0});
        st[1]=true;
        while (!queue.isEmpty()){
            int[] remove = queue.remove();
            int t=remove[0];
            int distmin=remove[1];
            st[t]=false;
            for (int i = h[t]; i != -1; i=ne[i]) {
                int j=e[i];
                if(dist[j]>distmin+w[i]){
                    dist[j]=distmin+w[i];
                    if(!st[j]){
                        st[j]=true;
                        queue.offer(new int[]{j,dist[j]});
                    }
                }
            }
        }
    }
    public static void dj2(){
        Arrays.fill(dist,0x3f3f3f3f);
        Arrays.fill(st,false);
        dist[1]=0;
        queue.offer(new int[]{1,0});
        st[1]=true;
        while (!queue.isEmpty()){
            int[] remove = queue.remove();
            int t=remove[0];
            int distmin=remove[1];
            st[t]=false;
            for (int i = h1[t]; i != -1; i=ne1[i]) {
                int j=e1[i];
                if(dist[j]>distmin+w1[i]){
                    dist[j]=distmin+w1[i];
                    if(!st[j]){
                        st[j]=true;
                        queue.offer(new int[]{j,dist[j]});
                    }
                }
            }
        }
    }
}
